﻿#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "defines.h"
#include "index.h"
#include "seg.h"
#include "mem_pool.h"

typedef struct
{
	HASH		hash_2, hash_3;
/*	bool		disk_loc_type     */
	PTR_DISK	disk_loc;
	int		last_slot_info;
	int		slot_cnt;
	PTR_KW		left_ptr, right_ptr;
} IDX_NODE;
/* IDX_NODE operations: */
static	HASH		_get_hash_2(PTR_KW);
static	HASH		_get_hash_3(PTR_KW);
static	PTR_KW		_get_left(PTR_KW);
static	PTR_KW		_get_right(PTR_KW);
static	PTR_DISK	_get_loc(PTR_KW);
static	int		_get_slot_cnt(PTR_KW);
static	int		_get_last_info(PTR_KW);
static	void 		_set_node_left(PTR_KW cur_ptr, PTR_KW new_ptr);
static	void		_set_node_right(PTR_KW cur_ptr, PTR_KW new_ptr);
static	void		_set_node_left_null(PTR_KW);
static	void		_set_node_right_null(PTR_KW);
static	void 		fill_idx_node(PTR_KW, HASH, HASH, PTR_DISK, int slot_cnt, int last_slot_info);


static	SEG_TABLE*	free_idx_nodes=NULL;
static	int		_max_page_id;
static	int		_iterm_horizon;
static	PTR_DISK	_ptr_disk;

static	PTR_KW*		ht_table;  /* point to THE_IMAGE */
static	IDX_NODE* 	idx_nodes;
static	PTR_KW*		idx_horizon;

/* pay attention to: reuse, re_init. */
static	PTR_KW		cur_ptr;
static	PTR_KW		pre_ptr, next_ptr;
static	HASH		hash_1, hash_2, hash_3; 
static	HASH		cur_hash_2, cur_hash_3;
static	int		dir;

static	FILE*		log_file=NULL;	
static	char*		g_image=NULL;

/*
 * _search_by_hash()
 * INPUT:  cur_ptr, pre_ptr, hash_X  ( XXX: cur_ptr must NOT be PTR_KW_NULL )
 * OUTPUT: cur_ptr, pre_ptr, next_ptr
 *	   cur_hash
 */
static	void		_search_by_hash();
static	int		_cmp();

static	PTR_KW		_get_free_idx_node();
static	void		_put_free_idx_node(PTR_KW* _ptr);
	HASH		hash_func_1(char* key, int key_len);
	HASH		hash_func_2(char* key, int key_len);
	HASH		hash_func_3(char* key, int key_len);

STATE idx_init(INIT_TYPE init_type, char* image, char* index_log, PTR_DISK disk_vol_in_chunk)
{
	int i;
	STATE state;
	
	g_image=image;

	/* open index_log */
	if (index_log)
	{
		log_file=fopen(index_log, "w");
		if (log_file==NULL)
		{
			printf ("error no: Create %s failed\n", index_log);
			return IDX_INIT_FAIL;
		}
	}
	if (image==NULL)
	{
		fprintf(log_file, "index init failed: invalid image.\n");
		return IDX_INIT_FAIL;
	}
	if (disk_vol_in_chunk<0 || disk_vol_in_chunk-DISK_IMAGE_SIZE-DISK_SEG_SIZE<200 || disk_vol_in_chunk>(1<<26) )  /* 200 is non-meaning magic number */
	{
		fprintf (log_file, "index init failed: too tiny/huge disk_vol chunk size:%d (%dG).\n", disk_vol_in_chunk, disk_vol_in_chunk/1024/64);
		return IDX_INIT_FAIL;
}
		

	free_idx_nodes=seg_create(SEG_TABLE_INIT_NR, KV_PAGE_SIZE, PTR_KW_SIZE);
	if (free_idx_nodes==NULL)
	{
		fprintf (log_file, "free_idx_nodes: seg create failed.\n");
		return IDX_INIT_FAIL;
	}
	

	if (init_type==INIT_TYPE_LOAD)
	{
		/* load SEG_INFO (3) */
		/* load to free_idx_nodes */
		//read from disk
		state=sync_read(DISK_IMAGE, g_image, IMAGE_K_SIZE*1024);
		printf ("sync_read:state:%d\n",state);
		fflush(stdout);

		_max_page_id=*((int*)(g_image+IMAGE_K_BASIS*1024+IMAGE_SEG_INFO));
		_iterm_horizon=*((int*)(g_image+IMAGE_K_BASIS*1024+IMAGE_SEG_INFO+4));
		_ptr_disk=*((PTR_DISK*) (g_image+IMAGE_K_BASIS*1024+IMAGE_SEG_INFO+8));

		printf ("_max_page_id:%d\t_iterm_horizon:%d\tptr_disk:%d\n", _max_page_id, _iterm_horizon, _ptr_disk);
		seg_load(&free_idx_nodes, _ptr_disk, _max_page_id);
	}
	else         /* init_type==INIT_TYPE_CREATE */
	{
		_max_page_id=0;
		_iterm_horizon=0;
		_ptr_disk=disk_vol_in_chunk-DISK_SEG_SIZE;  /***/
	}

	free_idx_nodes->iterm_horizon=_iterm_horizon;
	idx_horizon=(PTR_KW*)(g_image+IMAGE_K_BASIS*1024+IMAGE_IDX_HORIZON);
	ht_table=(PTR_KW*)(g_image+IMAGE_K_BASIS*1024+IMAGE_HT_TABLE);
	idx_nodes=(IDX_NODE*)(g_image+IMAGE_K_IDX_NODE*1024);

	if (init_type==INIT_TYPE_CREATE)
	{
		for (i=0; i<HT_TABLE_SIZE; i++) 
            ht_table[i]=IDX_NODE_NULL;
		*idx_horizon==0;
	}

	if (log_file)
	{
		fprintf (log_file, "idx init type: %s\n", init_type==INIT_TYPE_LOAD?"load":"create");
		fprintf (log_file, "free_idx_node: max_page_id:%d\t_iterm_horizon:%d\t_ptr_disk:%d\n", free_idx_nodes->cur_page_id, free_idx_nodes->iterm_horizon, _ptr_disk);
		fprintf (log_file, "_idx_horizon:%d\n", *((int*)idx_horizon) );
		fprintf (log_file, "ht_table init test [10024]:%d\n", ht_table[10024]);
		fflush(log_file);
	}

	return IDX_INIT_SUCCESS;
}

	

void idx_exit()
{
	int *p;
	STATE state;
	
	_max_page_id=free_idx_nodes->cur_page_id;
	_iterm_horizon=free_idx_nodes->iterm_horizon;

	p=(int*)(g_image+IMAGE_K_BASIS*1024+IMAGE_SEG_INFO);
	*p=_max_page_id;  p++;
	*p=_iterm_horizon;  p++;
	*p=_ptr_disk;

	seg_save(free_idx_nodes, _ptr_disk);
	if (log_file)
	{
		fprintf (log_file, "EXIT: free idx node (seg) save done.\n");
		fflush(log_file);
	}
	printf ("idx_exit:max_page_id:%d\titerm_horizon:%d\tptr_disk:%d\n", _max_page_id, _iterm_horizon, _ptr_disk);



	state=sync_write(0, g_image, IMAGE_K_SIZE*1024);
	printf ("exit: sync_write state:%d\n", state);
	if (log_file) 
	{
		fprintf (log_file, "EXIT: image sync done.\n");
		fprintf (log_file, "EXIT: close log_file ....\n");
		fclose(log_file);
	}

	log_file=NULL;
}

STATE idx_search(char* key, int key_len, PTR_DISK* disk_location, int* slot_cnt, int* last_slot_info)
{
	int table_id=0;
	table_id= hash_func_1(key, key_len) % HT_TABLE_MOD;
	hash_2=hash_func_2(key, key_len);
	hash_3=hash_func_3(key, key_len); /* it will need */
	if (log_file) fprintf (log_file, "Search: %-15s,  %-7d\t%-10x\t%-10x\t",key, table_id, hash_2, hash_3);

	cur_ptr=ht_table[table_id];
	if (cur_ptr==IDX_NODE_NULL) 
	{
		if (log_file) fprintf (log_file, "[failed]\n");
		return IDX_NODE_NOT_EXIST;
	}

	_search_by_hash();
	if ( _cmp()!=0 )
	{
		if (log_file) fprintf (log_file, "[failed]\n");
		return IDX_NODE_NOT_EXIST;
	}

	*disk_location=_get_loc(cur_ptr);
	*last_slot_info=_get_last_info(cur_ptr);  
	*slot_cnt=_get_slot_cnt(cur_ptr);

	if (log_file) fprintf (log_file, "disk_loc: %-15d last_info: %-15d slot_cnt: %-15d\t...[OK]\n", *disk_location, *last_slot_info, *slot_cnt);
	return IDX_SUCCESS;
}
		

STATE idx_insert(char* key, int key_len, PTR_DISK disk_location, int slot_cnt, int last_slot_info)
{
	int cmp;
	int table_id=0;
	PTR_KW new_ptr;
	table_id= hash_func_1(key, key_len) % HT_TABLE_MOD;
	
	hash_2=hash_func_2(key, key_len);
	hash_3=hash_func_3(key, key_len); /* it will need */

	if (log_file) fprintf (log_file, "INSERT: %-15s, disk_location: %-15d\tslot_cnt: %-15d\tlast_info: %-15d\t%-10x\t%-10x ........",key, disk_location, slot_cnt, last_slot_info, hash_2, hash_3);

	cur_ptr=ht_table[table_id];
	if (cur_ptr==IDX_NODE_NULL)
	{
		new_ptr=_get_free_idx_node();
		fill_idx_node(new_ptr, hash_2, hash_3, disk_location, slot_cnt, last_slot_info);
		ht_table[table_id]=new_ptr;	
		if (log_file) fprintf (log_file, "[OK]\n");
		return IDX_SUCCESS;
	}

	_search_by_hash();

	cmp=_cmp();
	if (cmp==0) 
	{
		if (log_file) fprintf (log_file, "[FAILED]\n");
		return IDX_NODE_EXIST;
	}

	new_ptr=_get_free_idx_node();
	fill_idx_node(new_ptr, hash_2, hash_3, disk_location, slot_cnt, last_slot_info);
	if (cmp<0) _set_node_left(cur_ptr, new_ptr);
	else _set_node_right(cur_ptr, new_ptr);

	if (log_file) fprintf (log_file, "[OK]\n");
	return IDX_SUCCESS;
}

/* dir==0  -->  pre_ptr==table_id */
static PTR_DISK _idx_delete(PTR_KW pre_ptr, PTR_KW cur_ptr, int dir)
{
	PTR_KW left_ptr, right_ptr;
	PTR_KW right_left_ptr, pre_right_left_ptr;
	left_ptr=_get_left(cur_ptr);
	right_ptr=_get_right(cur_ptr);

	if (left_ptr==IDX_NODE_NULL && right_ptr==IDX_NODE_NULL)
	{
		if (dir==0) ht_table[pre_ptr]=IDX_NODE_NULL;
		else if (dir==-1) _set_node_left_null(pre_ptr);
		else _set_node_right_null(pre_ptr);
		_put_free_idx_node(&cur_ptr);
		return _get_loc(cur_ptr);
	}

	if (left_ptr!=IDX_NODE_NULL && right_ptr!=IDX_NODE_NULL)
	{
		pre_right_left_ptr=right_left_ptr=right_ptr;
		while (_get_left(right_left_ptr)!=IDX_NODE_NULL)
		{
			//printf ("here!_2\n");
			pre_right_left_ptr=right_left_ptr;
			right_left_ptr=_get_left(pre_right_left_ptr);
		}

		if (right_left_ptr==pre_right_left_ptr)
		{
			/* case 1 */
			//printf ("here!_3\n");
			//printf ("cur_ptr:%d\tpre_ptr:%d\tdir:%d\n",_get_loc(cur_ptr), _get_loc(pre_ptr), dir);
			if (dir==0) ht_table[pre_ptr]=right_ptr;
			else if (dir==-1) _set_node_left(pre_ptr, right_ptr);
			else _set_node_right(pre_ptr, right_ptr);	
			_set_node_left(right_ptr, left_ptr);
			_put_free_idx_node(&cur_ptr);
			return _get_loc(cur_ptr);
		}	
		
		//printf ("here!_4\n");
		if (dir==0) ht_table[pre_ptr]=right_left_ptr;
		else if (dir==-1) _set_node_left(pre_ptr, right_left_ptr);
		else _set_node_right(pre_ptr, right_left_ptr);
		_set_node_left(right_left_ptr, left_ptr);
		_set_node_right(right_left_ptr, right_ptr);
		_set_node_left_null(pre_right_left_ptr); 

		return _get_loc(cur_ptr);
	}

	if (left_ptr!=IDX_NODE_NULL)
	{
		if (dir==0) ht_table[pre_ptr]=left_ptr;
		else if (dir==-1) _set_node_left(pre_ptr, left_ptr);
		else _set_node_right(pre_ptr, left_ptr);
		_put_free_idx_node(&cur_ptr);
		return _get_loc(cur_ptr);
	}

	if (right_ptr!=IDX_NODE_NULL)
	{
		if (dir==0) ht_table[pre_ptr]=right_ptr;
		else if (dir==-1) _set_node_left(pre_ptr, right_ptr);
		else _set_node_right(pre_ptr, right_ptr);
		_put_free_idx_node(&cur_ptr);
		return _get_loc(cur_ptr);
	}

	return 0;
}


STATE idx_delete(char* key, int key_len, PTR_DISK* disk_location)
{
	int table_id=0;
	table_id=hash_func_1(key, key_len) % HT_TABLE_MOD;
	hash_2=hash_func_2(key, key_len);
	hash_3=hash_func_3(key, key_len);

	if (log_file) fprintf (log_file, "DELETE: %15s ........", key);

	cur_ptr=ht_table[table_id];
	if (cur_ptr==IDX_NODE_NULL) return IDX_NODE_NOT_EXIST;
	if (_cmp()==0) 
	{
		*disk_location=_idx_delete(table_id, cur_ptr, 0);

		if (log_file) fprintf (log_file, " [OK]\n");
		return IDX_SUCCESS;
	}	

	_search_by_hash();
	if (_cmp()!=0)
	{
		if (log_file) fprintf (log_file, " [FAILED]\n");
		return IDX_NODE_NOT_EXIST;
	}

	/*_cmp()==0 */
	*disk_location=_idx_delete(pre_ptr, cur_ptr, dir);

	if (log_file) fprintf (log_file, " [OK]\n");
	return IDX_SUCCESS;
}



static void _dfs(int cur, int _dfs_level);
void  idx_show()
{
	int i;
	printf ("\n---------------------index show--------------------\n");
	for (i=0; i<=HT_TABLE_MOD; i++)
	{
		if (ht_table[i]==IDX_NODE_NULL) continue;
		printf ("table_id:%d\n",i);
		_dfs(ht_table[i],0);
		printf ("\n");
	}
	printf ("-----------------------------------------------------\n");
}

static void _dfs(int cur, int _dfs_level)
{
	int i;
	for (i=0; i<_dfs_level; i++) printf ("-");
	if (cur==IDX_NODE_NULL){ printf ("\n"); return;}
	

	printf ("DFS:  [%d  %d] [%d]\n", _get_hash_2(cur), _get_hash_3(cur), _get_loc(cur) );

	_dfs(_get_left(cur), _dfs_level+1);
	_dfs(_get_right(cur), _dfs_level+1);
}



/****************************************************************************************/

static int _cmp()
{
	cur_hash_2=_get_hash_2(cur_ptr);
	if (cur_hash_2==hash_2)
	{
		cur_hash_3=_get_hash_3(cur_ptr);
		if (cur_hash_3==hash_3) return 0;
		if (hash_3 < cur_hash_3) return -1;
		return 1;
	}
	if (hash_2<cur_hash_2) return -1;
	return 1;
}

static void _search_by_hash()
{
	int cmp;
	next_ptr=IDX_NODE_NULL;
	pre_ptr=IDX_NODE_NULL;
	cmp=_cmp();
	if (cmp==0) return;
	if (cmp<0) next_ptr=_get_left(cur_ptr), dir=-1;
	else next_ptr=_get_right(cur_ptr), dir=1;
	
	while (next_ptr!=IDX_NODE_NULL)
	{
		pre_ptr=cur_ptr;
		cur_ptr=next_ptr;
		next_ptr=IDX_NODE_NULL;
		cmp=_cmp();
		if ( cmp<0 ) next_ptr=_get_left(cur_ptr),dir=-1;
		else if (cmp > 0) next_ptr=_get_right(cur_ptr), dir=1;
		else break;
	}
}


PTR_KW _get_free_idx_node()
{
	/* idx_horizon */
	
	PTR_KW new_ptr;		
	PTR_KW i;
again:
	new_ptr=IDX_NODE_NULL;
	seg_get_iterm(free_idx_nodes , (char*)&new_ptr);

	if (new_ptr==IDX_NODE_NULL)
	{
		if (*idx_horizon>=IDX_NODE_FULL)
		{
			fprintf (log_file, "idx_horzion full\n");
			exit(1);
		}	
	
		for (i=(*idx_horizon); i<(*idx_horizon)+IDX_NODE_INCREASE; i++)
		{
			seg_put_iterm(&free_idx_nodes, (char*)&i);	
		}			
		*idx_horizon+=IDX_NODE_INCREASE;
		goto again;
	}
	
	return new_ptr;
}


void _put_free_idx_node(PTR_KW* _ptr)
{
	seg_put_iterm(&free_idx_nodes, (char*)_ptr);
}

/***************************************************************************************/

HASH _get_hash_2(PTR_KW ptr)
{
	return idx_nodes[ptr].hash_2;
}
HASH _get_hash_3(PTR_KW ptr)
{
	return idx_nodes[ptr].hash_3;
}

PTR_KW	_get_left(PTR_KW ptr)
{
	return idx_nodes[ptr].left_ptr;
}

PTR_KW	_get_right(PTR_KW ptr)
{
	return idx_nodes[ptr].right_ptr;
}

PTR_DISK  _get_loc(PTR_KW ptr)
{
	return idx_nodes[ptr].disk_loc;
}

int _get_slot_cnt(PTR_KW ptr)
{
	return idx_nodes[ptr].slot_cnt;
}


int  _get_last_info(PTR_KW ptr)
{
	return idx_nodes[ptr].last_slot_info;
}

void  _set_node_left(PTR_KW cur_ptr, PTR_KW new_ptr)
{
	idx_nodes[cur_ptr].left_ptr=new_ptr;
}

void  _set_node_right(PTR_KW cur_ptr, PTR_KW new_ptr)
{
	idx_nodes[cur_ptr].right_ptr=new_ptr;
}

void  _set_node_left_null(PTR_KW cur_ptr)
{
	idx_nodes[cur_ptr].left_ptr=IDX_NODE_NULL;
}

void  _set_node_right_null(PTR_KW cur_ptr)
{
	idx_nodes[cur_ptr].right_ptr=IDX_NODE_NULL;
}


void  fill_idx_node(PTR_KW cur_ptr, HASH hash_2, HASH hash_3, PTR_DISK disk_location, int slot_cnt, int last_slot_info)
{
	idx_nodes[cur_ptr].hash_2=hash_2;
	idx_nodes[cur_ptr].hash_3=hash_3;
	idx_nodes[cur_ptr].disk_loc=disk_location;
	idx_nodes[cur_ptr].slot_cnt=slot_cnt;
	idx_nodes[cur_ptr].last_slot_info=last_slot_info;
	idx_nodes[cur_ptr].left_ptr=IDX_NODE_NULL;
	idx_nodes[cur_ptr].right_ptr=IDX_NODE_NULL;	
}

/***************************************************************************************/


HASH hash_func_1(char* str, int key_len)
{
	unsigned int hash = 5381;
	while (*str)
	{
		hash += (hash << 5) + (*str++);
	}
 
	return (hash & 0x7FFFFFFF);
}

HASH hash_func_2(char* str, int key_len)
{
	int hash = 0;
	int x	= 0;
 
	while (*str)
	{
		hash = (hash << 4) + (*str++);
		if ((x = hash & 0xF0000000L) != 0)
		{
			hash ^= (x >> 24);
			hash &= ~x;
		}
	}

	return hash;
}

HASH hash_func_3(char* str, int key_len)
{
	int hash = 0;
	int i;
 
	for (i=0; *str; i++)
	{
		if ((i & 1) == 0)
		{
			hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
		}
		else
		{
			hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
		}
	}
 
	return hash;
}



